import java.util.PriorityQueue;

/**
 * 295. Find Median From Data Stream 数据流中的中位数
 * https://leetcode.com/problems/find-median-from-data-stream/description/
 */

/**
 * 方法：使用两个堆来维护数据流的中位数，left是一个最大堆，right是一个最小堆。通过保持两个堆的大小平衡来快速获取中位数。
 * 
 * Args:
 *   num (int): 要添加到数据流中的数字
 * 
 * Returns:
 *   double: 当前数据流的中位数
 * 
 * Time:
 *   addNum: O(log n) - 每次插入需要堆操作
 *   findMedian: O(1) - 直接访问堆顶元素
 * 
 * Space:
 *   O(n) - 需要存储所有输入数字
 */
class MedianFinder {
    private final PriorityQueue<Integer> left;
    private final PriorityQueue<Integer> right;

    public MedianFinder() {
        left = new PriorityQueue<>((a, b) -> b - a); //最大堆
         right = new PriorityQueue<>(); //最小堆
    }

    public void addNum(int num) {
        if(left.size() == right.size()){
            right.offer(num);
            left.offer(right.poll());
        }else{
            left.offer(num);
            right.offer(left.poll());
        }
    }

    public double findMedian() {
        if(left.size() > right.size()){
            return left.peek();
        }
        return (left.peek() + right.peek()) / 2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */